8bitfiles.net/archives

home *** CD-ROM | disk | FTP | other *** search

/ 8bitfiles.net/archives / archives.tar / archives / genie-commodore-file-library / Information / BCD.PART1.ARC / BCD PART 1

Wrap

Text File | 2019-04-13 | 31.1 KB | 634 lines

********************************************************************* This article is being presented through the *StarBoard* Journal of the FlagShip/StarShip, SIGS (Special Interest Groups) on the Delphi and GEnie telecommunications networks. Permission is hereby granted to non-profit organizations only to reprint this article or pass it along electronically as long as proper credit is given to both the author and the *StarBoard* Journal. ********************************************************************* THE ABC's OF BCD (part 1) Manipulating Decimal Numbers In Machine Language by W.J. Brier (TROUBLESOME on DELPHI) =========================================================================== INTRODUCTION Many tasks that are routinely performed in Commodore (CBM) BASIC can often be performed more efficiently in machine language. Tasks such as searching and sorting are performed in machine language at speeds many times that of BASIC and usually with less program overhead. Curiously, although many search, sort and file handling routines are coded in machine language, few decimal arithmetic and number handling machine language programs seem to be written. Perhaps the concept of doing math in machine language is too intimidating for most folks. Or maybe it's because the usual internal format of numbers is in binary notation. Whatever the cause of this "fear" it is actually unfounded. The MOS 65XX/85XX microprocessor (CPU) in your Commodore computer is equipped with instructions for doing elementary mathematical operations in decimal format. While performing math in machine language is not as simple as it is in BASIC it certainly is not beyond the capability of a reasonably proficient machine language programmer. This series of articles will attempt to remove some of the mystery surrounding decimal mathematics in machine language and will present programming examples illustrating machine language math techniques. Before we begin this discussion I would like to point out that this article series is not intended to teach elementary machine language programming techniques. Program examples presented herein are written with the assumption that the reader has some degree of familiarity with 65XX/85XX machine language programming. If you are not familiar with the 65XX/85XX instruction set, I recommend that you study one or more of several texts on the subject and follow the examples presented therein. If you are familiar with machine language techniques then the subject matter in this article will be understandable to you. Throughout this text the terms "ASCII decimal" and "decimal" may be interchangeably used, except in cases where confusion may occur. In either case, the term refers to the display form of the number being operated upon, which would be represented by a string of PETASCII characters. Credit for the source of some of the material to be presented herein must be extended to Lance A. Leventhal, whose excellent book 6502 ASSEMBLY LANGUAGE PROGRAMMING (Osborne/McGraw Hill) formed the basis of this article. Additional reference was made to PROGRAMMING THE 6502 by Rodney Zaks, in which a presentation of the concept of BCD notation is made. I. NUMBERING SYSTEMS Almost from the day that you first went to school you were (and still are) surrounded by the decimal number system. No doubt the decimal system developed because human beings have ten fingers with which to count. If we had been equipped with 16 fingers we'd probably be counting in hexadecimal (base 16). Decimal arithmetic is so ingrained in us that we routinely do calculations in decimal without ever actually pausing to consider just what it is we are doing. The designers of your computer were of course aware of this fact and programmed the BASIC interpreter so that it would handle ASCII decimal numbers. However, curious things occasionally happen in BASIC decimal arithmetic. You subtract two large numbers that are approximately equal to each other and the machine gives you an unexpected result. The result is very close to what it should be but is off by a tiny amount. This phenomenon occurs because the machine does not internally represent ASCII decimal numbers in decimal format. CBM BASIC stores numbers in one of two formats...normalized floating point binary, or two byte signed binary integers, neither in any way directly related to ASCII decimal notation. Decimal to binary conversion is performed because the most elementary functions within the machine are handled by simple YES/NO or ON/OFF operations, operations best performed in binary. When you ask BASIC to print the value of variable A for example, the value is converted from normalized floating point binary to ASCII decimal for display purposes only. Unfortunately, not all numbers will evenly convert from binary to decimal or vice versa. As a result, small but detectable errors will creep in and may result in display errors. This is not any fault of the machine or of BASIC but is a natural result of converting from one number base to another. The form of a normalized floating point binary number is not particularly easy to explain or understand. Basically, such a number consists of an implied mantissa with a value of one and a five byte exponent which represents some power of two. The sign of the number is carried along with this exponent. When the BASIC interpreter is called upon to display such a number it calls the FOUT subroutine located in the interpreter to decode and display the number. If a ASCII decimal number is assigned to a variable then the FIN routine is used to convert the number from decimal to floating point binary. It is these conversion operations that introduce errors. In many programs such conversion errors are of little consequence and are often ignored. However, some applications such as financial programs demand that the decimal amounts be exact, not approximate. In BASIC of course the programmer has to make do with the routines built into the interpreter. Although the same routines may be called in machine language there is really no good reason to do so (except for laziness on the part of the programmer) as the CPU has instructions for performing elementary decimal math. By using these instructions in an intelligent manner it is possible to handle the majority of the math problems that the average program might encounter. Additional use of logical operations in the CPU instruction set may be used to encode and decode numbers, just as the interpreter encodes and decodes numbers. In this article you will see how to build an internal numbering system that is based on decimal notation...one that will not introduce conversion errors when changing from one format to another. This system will be in what is referred to as BINARY CODED DECIMAL (BCD) notation. Unlike floating point binary there will be a direct relationship between a BCD number and its ASCII decimal equivalent. II. WHAT IS A BCD NUMBER? A BCD number is a ASCII decimal number that is represented by one or more BCD digits. Any BCD digit may have an unsigned ASCII decimal value of from 0 to 99. The range of a BCD number depends on the quantity of BCD digits used to represent that number (a sign can also be represented when signed numbers are required). A curious but nevertheless useful characteristic of a BCD digit is that in hexadecimal notation it looks just like the ASCII decimal number that it represents. A single BCD digit is evaluated by splitting it into a high and low nybble, the high nybble equivalent to the "tens" and the low nybble equivalent to the "units" of the ASCII decimal value represented by the BCD digit. Because two ASCII decimal digits are represented by a single BCD digit the format is said to be "packed" or "compressed". Let's look at some packed BCD digits and see the relationship between ASCII decimal, and the BCD decimal, hexadecimal and binary values: ASCII DEC HEX BINARY =================================================== 0 0 $00 %0000 0000 1 1 $01 %0000 0001 5 5 $05 %0000 0101 9 9 $09 %0000 1001 10 16 $10 %0001 0000 16 22 $16 %0001 0110 19 25 $19 %0001 1001 20 32 $20 %0010 0000 32 50 $32 %0011 0010 50 80 $50 %0101 0000 75 117 $75 %0111 0101 99 153 $99 %1001 1001 =================================================== The ASCII value is the value that you would actually display or input in your program. The other values are what the ASCII value would convert to in BCD format. Note that the hex equivalent appears to look just like the ASCII decimal value and that the "straight" decimal value seems to have little resemblance to the ASCII equivalent. One of the advantages of the BCD format is that certain types of numbers can be stored in less space than they would otherwise require in ASCII decimal format. For example, the time-of-day in ASCII decimal would require six bytes of storage (two for the hours, two for the minutes and two for the seconds). In BCD only three bytes would be required. A date such as 11-18-85, which would require eight bytes of storage, could be reduced to the BCD equivalent of: $11 $18 $85 which can be stored in only three bytes. However in many cases, a BCD number will consume more memory than a normalized floating binary equivalent would. In modern computers this is not a liability as copious amounts of memory are available for storage. The main advantage in using BCD notation is the fact that conversions between ASCII decimal and BCD are exact. There is no likelihood of a format conversion error as there would be in binary to decimal or vice versa. Also, conversions can performed much faster than floating binary to decimal conversions. No look-up tables are needed to transform a BCD digit to its ASCII decimal equivalent. The result is a neater and less cumbersome program. The next chapters will introduce the methods by which BCD numbers are organized and stored in RAM and converted from one format to the other. III. ORGANIZING AND STORING BCD NUMBERS When a ASCII decimal number is assigned from CBM BASIC to a variable, the interpreter converts and stores it as a five byte binary number. Regardless of the size of the ASCII decimal number that has been assigned to the variable it will always end up as five bytes. There are good reasons for this. It is much easier to perform mathematical operations if all of the numbers are of the same length and form. Also, when converting from one format to the other, a consistent length makes conversion less difficult. As with floating point binary notation, BCD notation is best fixed to a particular length. You, as the programmer, have the responsibility of determining just how long your BCD numbers are to be. The length is primarily governed by the desired place accuracy of the number (as is also the case with floating point binary). Therefore one of the first decisions to be made in coding the program is to determine the maximum size of the BCD numbers that are to be manipulated and then assign adequate storage space to accommodate them. Let's suppose that you are writing a financial program in which you will add and subtract dollar amounts. Let's further suppose that the maximum dollar amount that will have to be accommodated will be 9999.99 in ASCII decimal. In BCD this value would be notated as: $99 $99 $99 Part of your program's function will be to "know" where the decimal point is actually located (between the second and third BCD digits in the above example). For computational purposes the location of the decimal point will be unimportant. In converting from one format to the other however, you must know where that decimal point is to be placed. To store an ASCII decimal number in BCD format a byte of storage is required for every two ASCII digits. If you were to provide four bytes of storage you could then store a ASCII decimal equivalent of 999,999.99: $99 $99 $99 $99 So, you can see that there is a direct relationship between the desired place accuracy in ASCII decimal and the number of bytes required for the equivalent BCD storage. Also, a fundamental feature of BCD numbers is that they always represent even amounts of ASCII decimal digits, as can be seen from the above examples. If you want to limit the maximum ASCII decimal range to 99,999.99 you still have to supply four bytes of storage and simply ignore the high nybble of the first byte. Our value would then be: $09 $99 $99 $99 In this case the high nybble of the first byte is not actually used to represent a ASCII decimal digit and you can make alternate use of it to store a sign bit for the number. Let's suppose that the ASCII decimal value is now -99,999.99. You can represent that in BCD as: $89 $99 $99 $99 Hey, you say, where did that $89 come from? It is there because the seventh bit of that digit has been set to one, indicating that the BCD number is negative. Let's break that digit down into its binary equivalent for a closer look: $89 = %1000 1001 Note that the seventh bit of the number has been set to 1, thus giving the high nybble the value of $8. The low nybble has the value of $9. So, if you patch a high nybble of $8 to a low nybble of $9 you get a byte that is $89. Incidentally, the use of the % sign indicates a binary notated number, just as the $ sign indicates a number notated in hexadecimal. There is an excellent reason for using the seventh bit to indicate the sign of the number. If you load a CPU register with that digit and the sign bit is set, the N flag in the CPU status register will be set and you will immediately know that the number is negative. If the sign bit is cleared then the N flag will likewise clear. Using the BIT instruction on the first digit will also set or clear the N flag. As you will soon see, this feature will become quite useful when it comes time to actually evaluate BCD numbers for mathematical purposes. Regardless of the length of your BCD numbers the seventh bit of the first BCD digit will always act as the sign flag. If you have allotted four bytes in which to store the BCD number, you have set a ASCII decimal range of from -99,999.99 (assuming that you are handling dollars and cents values) to + 799,999.99, this range in BCD being represented as: -99,999.99 = $89 $99 $99 $99 799,999.99 = $79 $99 $99 $99 In binary the value of 799,999.99 would be: %0111 1001 %1001 1001 %1001 1001 %1001 1001 It is now apparent why the positive value of the number cannot exceed 799,999.99. The next value (800,000.00) would set the seventh bit of the first digit and the number would now be negative, resulting in an erroneous value. If your program requires a greater range simply allocate more storage for the BCD number. With the available RAM in the C-64 or C-128 gigantic numbers can be stored without resulting in any serious drain on the resources of the machine. For example, the number 10^100 can be stored in 50 bytes of RAM. If you were to display the ASCII decimal equivalent of this number on the C-64 it would use up almost three screen lines. Here is the number in ASCII decimal notation: 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000 Clearly, BCD notation permits you to store and represent numbers far greater than CBM BASIC would ever allow. When assigning memory storage for BCD numbers you should exercise some restraint in estimating the maximum size of the numbers to be stored. There is little point in assigning 20 bytes of RAM to store BCD numbers for use in a personal checking account program, as few individuals maintain a balance of 40 figures. The more BCD digits assigned to store a number the longer it will take to perform mathematical or conversion operations, as well as transfer numbers from one location in memory to another. Another factor to consider is the desired place accuracy to the right of the decimal point. Strictly speaking, in BCD notation the decimal point doesn't actually exist anywhere. The decimal point gets into the picture only when converting between ASCII decimal and BCD. However, when assigning memory for BCD storage, you must allow room for digits to the right of the decimal point in order to secure adequate place accuracy. For example, to store a range of numbers from +79,999,999.999999 to -9,999,999.999999 you would need seven bytes of storage, which would result in the following BCD numbers: $79 $99 $99 $99 $99 $99 $99 $99 $89 $99 $99 $99 $99 $99 $99 $99 Assigning this much storage results in resolution to a value of .000001 for each number to be stored. The imaginary decimal point would be located between the fifth and sixth BCD digits in each number (as shown by the extra space between the digits). Also note that the sign bit has been set on the second number, indicating that it is negative. Such storage must be assigned for each BCD number to be stored in your program. For convenience in simultaneously initializing (zeroing out) all values, the number storage areas should be in contiguous memory, as assigned by your assembler. In addition to storage for each of the BCD numbers to be used in your program you will need a work area for performing mathematical and conversion operations. This work area will consist of two BCD accumulators, an ASCII accumulator and two bytes of storage for sign flags for each BCD accumulator. Additional work space will be required if multiplication or division operations are to be performed. This additional area will be used for storing partial products or quotients. As with the actual storage for the BCD numbers, the accumulators, sign flags and partial product/quotient storage areas should be in contiguous RAM. Both BCD accumulators must be equal in size to each other and as large or larger than the size of the largest BCD number to be manipulated. Individual numbers may be smaller than the accumulators without incurring any problems in performing math operations. However, varying sizes of BCD numbers may make ASCII-BCD conversion more difficult to perform. It is recommended that all BCD numbers be stored in equal sized areas with the digit placement the same in all cases. The ASCII accumulator is used to convert between the BCD and ASCII formats. Its length must be equal to the largest ASCII string of digits to be displayed plus an additional three bytes of storage. These extra three bytes will containing the decimal point, the sign (if negative) and a zero byte terminator. For example, the ASCII decimal number -1234.56 would be stored in the ASCII accumulator as follows: HEX 2D 31 32 33 32 2E 35 36 00 ASCII - 1 2 3 4 . 5 6 The zero byte at the end of the ASCII string acts as a terminator and facilitates transferring or displaying the number. It indicates the end of the ASCII string (a zero byte in Commodore computers has no significance other than setting the Z flag in the CPU when loading the zero into a register). This feature will be quite useful in moving ASCII strings from one place to another in memory. With the matter of storage considered, attention will now be focused on conversion between ASCII and BCD format. The following symbols will be used during these discussions: SYMBOL REPRESENTS LENGTH ========================================== ACUM1 BCD Accumulator #1 4 ACUM2 BCD Accumulator #2 4 ACUMA ASCII Accumulator 10 SFLG1 ACUM1 Sign flag 1 SFLG2 ACUM2 Sign flag 1 .A CPU Accumulator -- .X CPU X Register -- .Y CPU Y Register -- ========================================== In addition to their primary duties of storing the sign of the number in their respective accumulators the two sign flags will also be used for temporary storage when converting between ASCII and BCD. For the purpose of discussion it will be assumed that each BCD accumulator is four bytes in length, as are all BCD numbers referenced in the program examples. The ASCII accumulator will be an assumed length of ten bytes, including the terminator byte ($00). Means by which the ASCII value in ACUMA is transferred to or fetched from memory will be discussed in another chapter. IV. CONVERTING TWO ASCII DIGITS TO A BCD DIGIT As mentioned before there is a "two for one" relationship between ASCII numbers and their BCD equivalents. Therefore, conversion from ASCII to BCD is predicated on the concept of transferring two ASCII digits into a single BCD digit. This implies of course that all ASCII numbers in a BCD-based system contain an even number of digits. In those cases where the ASCII number is represented by an odd number of digits means must be developed to substitute an ASCII zero ($30) for the "missing" digit. For our initial example we will assume that the conversion will be per- formed on two ASCII digits: 57 If our conversion is correct we should be left with the single BCD digit: $57 Conversion of two ASCII digits to a BCD digit is accomplished in logical steps: 1. Load the .A register with the lower of the two ASCII digits (the "units") and load the .X register with the higher digit (the "tens"); 2. Change the byte in the .A register from an ASCII value to a binary value and store it in RAM; 3. Transfer the byte in the .X register to the .A register and change it from ASCII to binary; 4. Left shift the binary value to the high nybble position in the .A register; 5. Logically OR the .A register with the units nybble that was stored in RAM. The BCD digit is now in the .A register. For ease of use within your program steps 2 through 6 should be structured into a subroutine, which we will refer to with the symbol ASBCD in this discussion. Then, whenever you need to convert two ASCII digits to BCD, simply use the following code: LDA UNITS ;ASCII "UNITS" LDX TENS ;ASCII "TENS" JSR ASBCD ;CALL CONVERSION ROUTINE STA ------ ;STORE BCD DIGIT IN RAM The subroutine ASBCD would be structured as follows: ASBCD SEC SBC #$30 ;ASCII TO BINARY STA SFLG2 ;STORE IN RAM ; SEC TXA ;MOVE TENS TO .A REGISTER SBC #$30 ;ASCII TO BINARY ; ASL A ;LEFT-SHIFT LOW NYBBLE... ASL A ;TO HIGH NYBBLE POSITION ASL A ASL A ; ORA SFLG2 ;COMBINE WITH LOW NYBBLE ; RTS ;BCD DIGIT IS IN .A REGISTER Upon exiting this subroutine the .A register will contain the BCD digit, the .X register will still contain the ASCII "tens" digit and the .Y register will be unchanged. The subroutine as presented makes no attempt to filter out non-numeric ASCII characters (hex values outside of the range of $30 through $39). This should be performed by the portion of your program that fetches the ASCII number. Let's see exactly what this subroutine does to the values presented to it. The ASCII decimal number 57 is to be encoded into BCD. The first step is to change the ASCII units value ($37) to binary. This is simply accomplished by subtracting $30 from the .A register, the result ($07) being temporarily stored in RAM. Next, the tens value ($35) is moved to the .A register and $30 is subtracted from it resulting in a value of $05. The four ASL operations shift the $05 to the left until the .A register finally contains $50. Each shift would look like this in binary: .A Register 0000 0101 1st shift 0000 1010 2nd shift 0001 0100 3rd shift 0010 1000 4th shift 0101 0000 The result is that the value formerly contained in the low nybble is now in the high nybble and the low nybble is set to zero. The final step is to logically OR the .A register with the low nybble saved at SFLG2, resulting in the value $57 being left in the .A register. Here is what the process would look like in binary: .A Register 0101 0000 = $50 ORA SFLG2 0000 0111 = $07 =============================== .A Register 0101 0111 = $57 The ASCII decimal number 57 has been converted to the BCD digit $57 and is in the .A register awaiting storage. It is apparent from studying this routine that the ASCII number to be converted must be two digits in length. If it is a single digit number then the .X register must be loaded with $00. For example, the ASCII number 7 would convert to $07 in this routine. To avoid an odd number of digits in the ASCII number the ASCII string should be left and/or right padded with zeros to achieve an even number of digits. For the sake of easy conversion the padding should be such that all ASCII numbers are identical in length. Means to accomplish this will be discussed later on. V. CONVERTING A BCD DIGIT TO TWO ASCII DIGITS The previous chapter presented the method of encoding two ASCII digits into a single BCD digit. The reverse operation, decoding a BCD digit into two ASCII digits, will now be discussed. Because the BCD digit is only a single value, logical operations are required to separate the high and low nybbles so that they can be individually extracted and changed from binary to ASCII, just as logical operations were required to originally create the digit. Thus the operation is the reverse of the encoding routine presented in ASBCD. The decoding routine will be called (logically enough) BCDAS. Essentially, the procedure is as follows: 1. Load the .A register with the BCD digit to be decoded; 2. Save the BCD value on the stack; 3. Extract the low nybble from the BCD value, convert it from binary to ASCII and save it in the .X register; 4. Fetch the original BCD value from the stack and shift the high nybble to the low nybble position; 5. Convert the low nybble from binary to ASCII. This will result in the .A register containing the tens in ASCII format and the .X register containing the units (also in ASCII format). As before, steps 2 through 5 should be structured into a subroutine so that it may be called from anywhere in your program. Then, when you need to decode a BCD digit you can use the following sequence: LDA BCD ;FETCH BCD DIGIT TO DECODE JSR BCDAS ;DECODE STA ------ ;SAVE TENS STX ------ ;SAVE UNITS The subroutine BCDAS would look like this: BCDAS PHA ;SAVE BCD VALUE ON STACK ; AND #$0F ;MASK HIGH NYBBLE CLC ADC #$30 ;BINARY TO ASCII TAX ;SAVE UNITS IN .X ; PLA ;FETCH BCD VALUE FROM STACK ; LSR A ;SHIFT HIGH NYBBLE TO... LSR A ;LOW NYBBLE POSITION LSR A LSR A ; CLC ADC #$30 ;BINARY TO ASCII ; RTS ;EXIT Upon exit from this routine the .A register will contain the tens, the .X register will contain the units and the .Y register will be unchanged. No RAM is used to execute this routine. If the high nybble of the BCD value was zero (as in $07) the .A register will contain an ASCII zero ($30). Let's see how this routine operates on a BCD digit. We'll assume that the BCD value of $57 is to be decoded. After saving the BCD value on the stack the first step is to logically AND the .A register with $0F, thus masking the high nybble: .A Register 0101 0111 = $57 AND #$0F 0000 1111 = $0F =============================== .A Register 0000 0111 = $07 Adding $30 to .A results in a value of $37 which is 7 in ASCII. This value is transferred to the .X register and becomes the units value. Next the BCD value is fetched from the stack and subjected to four LSR operations, each of which shift the high nybble one bit to the right until it becomes the low nybble. This results in the following series of values: .A Register 0101 0111 1st Shift 0010 1011 2nd Shift 0001 0101 3rd Shift 0000 1010 4th Shift 0000 0101 The high nybble is now equal to zero and the low nybble is now equal to $05. Adding $30 results in a value of $35 being left in the .A register. Therefore, upon exit from the BCDAS subroutine .A will contain $35 or ASCII 5 and .X will contain $37 or 7 in ASCII. The two digits together result in ASCII 57. It is apparent that regardless of the BCD value passed to the BCDAS subroutine two ASCII digits will always result. In the process of decoding a BCD number (which would be four bytes long in our examples) it possible that some leading and/or trailing zeros may result. A routine to strip leading and trailing zeros from ASCII numbers will be presented in a later chapter. VI. RECAP Up to this point you have learned what a BCD number is, how to properly organize and store BCD numbers and how to convert ASCII digits to BCD and vice versa. Program examples were listed illustrating techniques to make the necessary conversions from one format to the other. Before you proceed beyond this point, I suggest that you code the examples into the computer using a machine language monitor and run the examples and see what happens. Don't be afraid of accidentally crashing the machine. You won't hurt anything and may learn a lesson or two from it. Pass various values to the decoding and encoding routines and see what the routines return in the registers. You should terminate your code with a BRK instruction so that control is returned to the monitor when the code has been executed. Pick anywhere in RAM for the storage needed in ASBCD (which is SFLG2) and examine SFLG2 upon termination of the routine to see what is left. Only by experimenting with these routines will you gain full understanding of how they work. THE ABC'S OF BCD part 2 will cover techniques for encoding and decoding multiple byte numbers, and the stripping of leading and trailing zeros. A thorough understanding of the material just presented is essential to understanding part 2. If you are not sure of how a particular machine language op-code functions consult any good text on 65XX/85XX machine language programming for a clearer explanation. ------------------------------------------------------------------------ THE ABC'S OF BCD is copyrighted by W.J. Brier and is not to be sold in any form. Copies of this article may be distributed by any medium provided that full credit is given to the author.